#include <bits/stdc++.h>
using namespace std;
// 定义长整型别名
typedef long long ll;

int main() {
    // 解除标准输入输出流的同步，提高输入输出效率
    ios::sync_with_stdio(false);
    // 取消 cin 和 cout 的绑定，加快输入输出速度
    cin.tie(0);
    int n;
    // 输入数组的长度
    cin >> n;
    // 定义长度为 n 的长整型向量 a 用于存储数组元素
    vector<ll> a(n);
    // 循环输入数组的每个元素
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    // 定义长度为 n + 1 的长整型向量 s 用于存储前缀和，初始值都为 0
    vector<ll> s(n + 1, 0);
    // 计算前缀和
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i - 1];
    }
    int q;
    // 输入查询的次数
    cin >> q;
    // 定义整型向量 res 用于存储每次查询的结果
    vector<int> res;
    // 循环处理每次查询
    while (q--) {
        int l, u;
        // 输入查询的左边界 l 和参数 u
        cin >> l >> u;
        // 计算 k0 的值
        double k0 = (2.0 * u + 1) / 2.0;
        // 二分查找的左边界初始化为 l
        int low = l;
        // 二分查找的右边界初始化为 n
        int high = n;
        // 初始化满足条件的最大右边界为 l - 1
        int ans = l - 1;
        // 二分查找满足条件的最大右边界
        while (low <= high) {
            // 计算中间位置
            int mid = (low + high) / 2;
            // 计算从 l 到 mid 的区间和
            ll sum_mid = s[mid] - s[l - 1];
            if (sum_mid <= k0) {
                // 如果区间和小于等于 k0，更新满足条件的最大右边界
                ans = mid;
                // 缩小左边界，继续向右查找
                low = mid + 1;
            } else {
                // 如果区间和大于 k0，缩小右边界，向左查找
                high = mid - 1;
            }
        }
        // 定义一个存储候选结果的向量，元素为 pair 类型，包含右边界和对应的和
        vector<pair<int, ll>> candidates;
        if (ans >= l) {
            // 计算从 l 到 ans 的区间和
            ll k1 = s[ans] - s[l - 1];
            // 计算该区间的得分
            ll sum1 = k1 * (2LL * u - k1 + 1) / 2;
            // 将右边界 ans 和得分 sum1 作为候选结果加入向量
            candidates.emplace_back(ans, sum1);
            if (ans + 1 <= n) {
                // 计算从 l 到 ans + 1 的区间和
                ll k2 = s[ans + 1] - s[l - 1];
                // 计算该区间的得分
                ll sum2 = k2 * (2LL * u - k2 + 1) / 2;
                // 将右边界 ans + 1 和得分 sum2 作为候选结果加入向量
                candidates.emplace_back(ans + 1, sum2);
            }
        } else {
            // 计算从 l 到 l 的区间和
            ll k = s[l] - s[l - 1];
            // 计算该区间的得分
            ll sum_val = k * (2LL * u - k + 1) / 2;
            // 将右边界 l 和得分 sum_val 作为候选结果加入向量
            candidates.emplace_back(l, sum_val);
        }
        // 初始化最大得分
        ll max_sum = -1e18;
        // 初始化最优右边界
        int best_r = n + 1;
        // 遍历所有候选结果，找出得分最大且右边界最小的结果
        for (auto &p : candidates) {
            int r = p.first;
            ll current_sum = p.second;
            if (current_sum > max_sum || (current_sum == max_sum && r < best_r)) {
                // 更新最大得分和最优右边界
                max_sum = current_sum;
                best_r = r;
            }
        }
        // 将最优右边界加入结果向量
        res.push_back(best_r);
    }
    // 输出所有查询的结果
    for (size_t i = 0; i < res.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << res[i];
    }
    cout << '\n';
    return 0;
}